package org.raymond.iworks.study.basic.structure.linkedlist;

/**
 * @author raymond
 * @version V1.0
 * @Description: 约束问题:
 * 设编号1,2,...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,
 * 他的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生出一个出队编号的序列
 *
 * 提示:用一个不带头节点的循环链表来处理josephu问题.先构成一个有n个节点的单循环链表,
 * 然后由k节点起从1开始计数,计到m时,对应节点从链表中删除,
 * 然后再从被删除节点的下一个节点开始,又从1开始计数,直到最后一个节点从链表中删除
 */
/**
 * 分析:
 * 假设n=5,即有5个人,k=1,从第一个人开始报数,m=2,即数2下.
 * 最后只剩下一个人时,自己关联自己,也是一个循环,出队列过程如下:
 * init: 1->2->3->4->5->1
 * 第一轮: 1->2(出列), 1->3->4->5->1
 * 第二轮: 3->4(出列), 1->3->5->1
 * 第三轮: 5->1(出列), 3->5->3
 * 第四轮: 3->5(出列), 3->3
 * 第五轮: 3->3(出列), end
 * 出队顺序:2->4->1->5->3
 */
public class JosephuTest {
    public static void main(String[] args) {
        CircleSingleLinkedList list1 = new CircleSingleLinkedList();
        list1.add(5);
        list1.list();

        list1.count(1, 2, 5);

    }

    // 根据用户输入,生成一个节点出圈的顺序
    // 1. 需要创建一个辅助指针tmp,指向待出圈节点的前一个节点
    // 2. 报数时,first和辅助指针tmp同时移动m-1次,因为报数m次,移动m-1次.
    // 3. 将first指向的节点出圈
    // first = first.next
    // tmp.next = first
    // 原来first指向的节点就没有任何引用,会被自动回收
}
